package dynamic;

import java.util.Arrays;
//给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
//
// 说明：每次只能向下或者向右移动一步。
//
//
//
// 示例 1：
//
//
//输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
//输出：7
//解释：因为路径 1→3→1→1→1 的总和最小。
//
//
// 示例 2：
//
//
//输入：grid = [[1,2,3],[4,5,6]]
//输出：12
//
//
//
//
// 提示：
//
//
// m == grid.length
// n == grid[i].length
// 1 <= m, n <= 200
// 0 <= grid[i][j] <= 100
//
// Related Topics 数组 动态规划 矩阵 👍 1296 👎 0


/**
 * @author luo
 * @description
 * @since 2022/7/19 14:41
 */
public class MinLength {

    private int[][] cache;

    public static void main(String[] args) {
        int[][] arr = new int[][]{
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        MinLength minLength = new MinLength();
        int minPath = minLength.minPathSum(arr);
        System.out.println(minPath);
        for (int i = 0; i < minLength.cache.length; i++) {
            for (int j = 0; j < minLength.cache[i].length; j++) {
                System.out.print(minLength.cache[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public int minPathSum(int[][] grid) {
        cache = new int[grid.length][grid[0].length];

        return find(0, 0, grid);

    }

    private int find(int x, int y, int[][] grid) {
        if (x > grid.length - 1 || y > grid[0].length - 1) {
            return Integer.MAX_VALUE;
        }
        if (x == grid.length - 1 && y == grid[0].length - 1) {
            return cache[x][y] = grid[x][y];

        } else {
            int result = cache[x][y];
            if (result != 0) {
                return result;
            }
            int xPath = find(x + 1, y, grid);
            int yPath = find(x, y + 1, grid);
            result = Math.min(xPath, yPath);
            result += grid[x][y];
            cache[x][y] = result;
            return result;
        }
    }
}
